A Viterbi decoder determines a maximum likelihood path through a trellis created by a convolutional decoder. Use of a binary tree structure embedded within the De Bruijn graph implements the maximum likelihood decoding of convolutional codes. The system uses a pipelined algorithm for finding the smallest metric.
The Viterbi algorithm produces an output by finding the survivor path with the smallest metric. The smallest metric is found by sorting the performance metrics of all the survivor paths. This strategy has a better probability of correct decoding compared to the strategies that choose an arbitrary survivor path. The improvement is achieved with minimal hardware overhead. For a detailed description of convolutional codes and the Viterbi decoders, refer to a paper entitled The Viterbi Algorithm, by G. David Forney, Jr., published in the proceeding of the IEEE, Vol. 61, No. 3, March 3, 1973, Pages 268-278. For a description of the De Bruijn graph, see article entitled The De Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, by Samatham and Pradhan, IEEE Transactions on Computers, Vol. 38, No. 4, April 1989, which article is incorporated herein by reference. Copies of both papers are included in the information disclosure documents, .and is incorporated herein by reference.